//
//Copyright (C) 2002-2005  3Dlabs Inc. Ltd.
//All rights reserved.
//
//Redistribution and use in source and binary forms, with or without
//modification, are permitted provided that the following conditions
//are met:
//
//    Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//
//    Redistributions in binary form must reproduce the above
//    copyright notice, this list of conditions and the following
//    disclaimer in the documentation and/or other materials provided
//    with the distribution.
//
//    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
//    contributors may be used to endorse or promote products derived
//    from this software without specific prior written permission.
//
//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
//"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
//LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
//FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
//COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
//INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
//BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
//LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
//CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
//LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
//ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
//POSSIBILITY OF SUCH DAMAGE.
//

#ifndef _POOLALLOC_INCLUDED_
#define _POOLALLOC_INCLUDED_

#ifdef _DEBUG
#  define GUARD_BLOCKS  // define to enable guard block sanity checking
#endif

//
// This header defines an allocator that can be used to efficiently
// allocate a large number of small requests for heap memory, with the
// intention that they are not individually deallocated, but rather
// collectively deallocated at one time.
//
// This simultaneously
//
// * Makes each individual allocation much more efficient; the
//     typical allocation is trivial.
// * Completely avoids the cost of doing individual deallocation.
// * Saves the trouble of tracking down and plugging a large class of leaks.
//
// Individual classes can use this allocator by supplying their own
// new and delete methods.
//
// STL containers can use this allocator by using the pool_allocator
// class as the allocator (second) template argument.
//

#include <stddef.h>
#include <vector>

// If we are using guard blocks, we must track each indivual
// allocation.  If we aren't using guard blocks, these
// never get instantiated, so won't have any impact.
//

class TAllocation {
public:
	TAllocation(size_t size, unsigned char* mem, TAllocation* prev = 0) :
			size(size), mem(mem), prevAlloc(prev)
	{
		// Allocations are bracketed:
		//    [allocationHeader][initialGuardBlock][userData][finalGuardBlock]
		// This would be cleaner with if (guardBlockSize)..., but that
		// makes the compiler print warnings about 0 length memsets,
		// even with the if() protecting them.
#       ifdef GUARD_BLOCKS
		memset(preGuard(), guardBlockBeginVal, guardBlockSize);
		memset(data(), userDataFill, size);
		memset(postGuard(), guardBlockEndVal, guardBlockSize);
#       endif
	}

	void check() const
	{
		checkGuardBlock(preGuard(), guardBlockBeginVal, "before");
		checkGuardBlock(postGuard(), guardBlockEndVal, "after");
	}

	void checkAllocList() const;

	// Return total size needed to accomodate user buffer of 'size',
	// plus our tracking data.
	inline static size_t allocationSize(size_t size)
	{
		return size + 2 * guardBlockSize + headerSize();
	}

	// Offset from surrounding buffer to get to user data buffer.
	inline static unsigned char* offsetAllocation(unsigned char* m)
	{
		return m + guardBlockSize + headerSize();
	}

private:
	void checkGuardBlock(unsigned char* blockMem, unsigned char val,
			const char* locText) const;

	// Find offsets to pre and post guard blocks, and user data buffer
	unsigned char* preGuard() const
	{
		return mem + headerSize();
	}
	unsigned char* data() const
	{
		return preGuard() + guardBlockSize;
	}
	unsigned char* postGuard() const
	{
		return data() + size;
	}

	size_t size;                  // size of the user data area
	unsigned char* mem;           // beginning of our allocation (pts to header)
	TAllocation* prevAlloc;       // prior allocation in the chain

	// Support MSVC++ 6.0
	const static unsigned char guardBlockBeginVal;
	const static unsigned char guardBlockEndVal;
	const static unsigned char userDataFill;

	const static size_t guardBlockSize;
#   ifdef GUARD_BLOCKS
	inline static size_t headerSize() {return sizeof(TAllocation);}
#   else
	inline static size_t headerSize()
	{
		return 0;
	}
#   endif
};

//
// There are several stacks.  One is to track the pushing and popping
// of the user, and not yet implemented.  The others are simply a
// repositories of free pages or used pages.
//
// Page stacks are linked together with a simple header at the beginning
// of each allocation obtained from the underlying OS.  Multi-page allocations
// are returned to the OS.  Individual page allocations are kept for future
// re-use.
//
// The "page size" used is not, nor must it match, the underlying OS
// page size.  But, having it be about that size or equal to a set of
// pages is likely most optimal.
//
class TPoolAllocator {
public:
	TPoolAllocator(bool global = false, int growthIncrement = 8 * 1024,
			int allocationAlignment = 16);

	//
	// Don't call the destructor just to free up the memory, call pop()
	//
	~TPoolAllocator();

	//
	// Call push() to establish a new place to pop memory too.  Does not
	// have to be called to get things started.
	//
	void push();

	//
	// Call pop() to free all memory allocated since the last call to push(),
	// or if no last call to push, frees all memory since first allocation.
	//
	void pop();

	//
	// Call popAll() to free all memory allocated.
	//
	void popAll();

	//
	// Call allocate() to actually acquire memory.  Returns 0 if no memory
	// available, otherwise a properly aligned pointer to 'numBytes' of memory.
	//
	void* allocate(size_t numBytes);

	//
	// There is no deallocate.  The point of this class is that
	// deallocation can be skipped by the user of it, as the model
	// of use is to simultaneously deallocate everything at once
	// by calling pop(), and to not have to solve memory leak problems.
	//

protected:
	friend struct tHeader;

	struct tHeader {
		tHeader(tHeader* nextPage, size_t pageCount) :
#ifdef GUARD_BLOCKS
						lastAllocation(0),
#endif
						nextPage(nextPage), pageCount(pageCount)
		{
		}

		~tHeader()
		{
#ifdef GUARD_BLOCKS
			if (lastAllocation)
			lastAllocation->checkAllocList();
#endif
		}

		tHeader* nextPage;
		size_t pageCount;
#ifdef GUARD_BLOCKS
		TAllocation* lastAllocation;
#endif
	};

	struct tAllocState {
		size_t offset;
		tHeader* page;
	};
	typedef std::vector<tAllocState> tAllocStack;

	// Track allocations if and only if we're using guard blocks
	void* initializeAllocation(tHeader* block, unsigned char* memory,
			size_t numBytes)
	{
#       ifdef GUARD_BLOCKS
		new(memory) TAllocation(numBytes, memory, block->lastAllocation);
		block->lastAllocation = reinterpret_cast<TAllocation*>(memory);
#		else
		// TODO: UNUSED_ARG()
		(void) block;
		(void) numBytes;
#       endif

		// This is optimized entirely away if GUARD_BLOCKS is not defined.
		return TAllocation::offsetAllocation(memory);
	}

	bool global;            // should be true if this object is globally scoped
	size_t pageSize;        // granularity of allocation from the OS
	size_t alignment;       // all returned allocations will be aligned at
							//      this granularity, which will be a power of 2
	size_t alignmentMask;
	size_t headerSkip;      // amount of memory to skip to make room for the
							//      header (basically, size of header, rounded
							//      up to make it aligned
	size_t currentPageOffset;  // next offset in top of inUseList to allocate from
	tHeader* freeList;      // list of popped memory
	tHeader* inUseList;     // list of all memory currently being used
	tAllocStack stack;     // stack of where to allocate from, to partition pool

	int numCalls;           // just an interesting statistic
	size_t totalBytes;      // just an interesting statistic
private:
	TPoolAllocator& operator=(const TPoolAllocator&);  // dont allow assignment operator
	TPoolAllocator(const TPoolAllocator&);  // dont allow default copy constructor
};

//
// There could potentially be many pools with pops happening at
// different times.  But a simple use is to have a global pop
// with everyone using the same global allocator.
//
typedef TPoolAllocator* PoolAllocatorPointer;
extern TPoolAllocator& GetGlobalPoolAllocator();
#define GlobalPoolAllocator GetGlobalPoolAllocator()

struct TThreadGlobalPools {
	TPoolAllocator* globalPoolAllocator;
};

void SetGlobalPoolAllocatorPtr(TPoolAllocator* poolAllocator);

//
// This STL compatible allocator is intended to be used as the allocator
// parameter to templatized STL containers, like vector and map.
//
// It will use the pools for allocation, and not
// do any deallocation, but will still do destruction.
//
template<class T>
class pool_allocator {
public:
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T *pointer;
	typedef const T *const_pointer;
	typedef T& reference;
	typedef const T& const_reference;
	typedef T value_type;
	template<class Other>
	struct rebind {
		typedef pool_allocator<Other> other;
	};
	pointer address(reference x) const
	{
		return &x;
	}
	const_pointer address(const_reference x) const
	{
		return &x;
	}

#ifdef USING_SGI_STL
	pool_allocator() {}
#else
	pool_allocator() :
			allocator(&GlobalPoolAllocator)
	{
	}
	pool_allocator(TPoolAllocator& a) :
			allocator(&a)
	{
	}
	pool_allocator(const pool_allocator<T>& p) :
			allocator(p.allocator)
	{
	}
#endif

#ifdef _WIN32
	template<class Other>
#ifdef USING_SGI_STL
	pool_allocator(const pool_allocator<Other>& p) /*: allocator(p.getAllocator())*/{}
#else
	pool_allocator(const pool_allocator<Other>& p) : allocator(&p.getAllocator()) {}
#endif
#endif

#ifndef _WIN32
	template<class Other>
	pool_allocator(const pool_allocator<Other>& p) :
			allocator(&p.getAllocator())
	{
	}
#endif

#ifdef USING_SGI_STL
	static pointer allocate(size_type n) {
		return reinterpret_cast<pointer>(getAllocator().allocate(n));}
	pointer allocate(size_type n, const void*) {
		return reinterpret_cast<pointer>(getAllocator().allocate(n));}

	static void deallocate(void*, size_type) {}
	static void deallocate(pointer, size_type) {}
#else
	pointer allocate(size_type n)
	{
		return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
	}
	pointer allocate(size_type n, const void*)
	{
		return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
	}

	void deallocate(void*, size_type)
	{
	}
	void deallocate(pointer, size_type)
	{
	}
#endif

	pointer _Charalloc(size_t n)
	{
		return reinterpret_cast<pointer>(getAllocator().allocate(n));
	}

	void construct(pointer p, const T& val)
	{
		new ((void *) p) T(val);
	}
	/*
	 void destroy(pointer p) { p->T::~T(); }
	 */
	void destroy(const pointer p)
	{
		p->T::~T();
	}

	bool operator==(const pool_allocator& rhs) const
	{
		return &getAllocator() == &rhs.getAllocator();
	}
	bool operator!=(const pool_allocator& rhs) const
	{
		return &getAllocator() != &rhs.getAllocator();
	}

	size_type max_size() const
	{
		return static_cast<size_type>(-1) / sizeof(T);
	}
	size_type max_size(int size) const
	{
		return static_cast<size_type>(-1) / size;
	}

#ifdef USING_SGI_STL
	//void setAllocator(TPoolAllocator* a) { allocator = a; }
	static TPoolAllocator& getAllocator() {return GlobalPoolAllocator;}
#else
	void setAllocator(TPoolAllocator* a)
	{
		allocator = a;
	}
	TPoolAllocator& getAllocator() const
	{
		return *allocator;
	}

protected:
	TPoolAllocator *allocator;
#endif
};

#endif // _POOLALLOC_INCLUDED_
